模拟赛题解/2025.9.2 模拟赛

T1-删树游戏（game）

题面

有一棵由编号为 $1\sim n$ 的 个节点构成的有根树，其中 $1$ 为根节点，$i$ 号点的父亲为 $p_i$。此外，每个节点都有一个互不相同的整数权值，$i$ 号节点的权值为 $a_i$ 。保证 $a$ 为 $1\sim n$ 的一个排列。

我们从 $1$ 出发，每次移动到当前节点的子节点中权值最小的一个。如此重复，直到到达某个叶子节点。这样得到的路径记作 $S=[S_1,S_2,\cdots,S_k]$，我们称其为特殊路径。

定义一次删除操作如下：

• 设当前树的特殊路径为 $S=[S_1,S_2,\cdots,S_k]$。
• 令 $i$ 从 $1$ 到 $k-1$ ，依次执行：交换 $a_{S_i}$ 与 $a_{S_{i+1}}$。
• 删除树中 $S_k$ 与其父亲相连的边。

我们对这棵树进行 $n$ 次删除操作，你需要在每次操作前求出 $1$ 号点的权值 $a_1$。

$1\leq n\leq3\times10^5$。

题解

定义删除序列 $S$，$S_i$ 为这一棵树第 $i$ 操作前根节点的权值。

对于一个点 $u$，设它操作选中了子节点 $son$ 多次，那么 $a_{son}$ 的变化一定形如 $son$ 子树的删除序列。

那么求 $u$ 子树的操作序列相当于先加入 $a_u$，然后把子节点的删除序列归并起来。

注意到这个删除序列就是 $u$ 子树的一个 BFS 序，而且我们要最小化这个 BFS 序的权值的字典序。

用堆维护 BFS 即可。每次取出最小权值点后加入所有的子节点。

复杂度 $O(n\log n)$。

T2-身份猜测（identity）

题面

这是一道交互题。

现有 $n=a+b$ 个人，编号为 $0\sim n-1$。其中恰有 $a$ 个人是诚实的，$b$ 个人是不诚实的。每个人都清楚所有人的身份，但你知道的仅有 $a$ 和 $b$ 的值。你需要去确定每个人的身份。

如果你在已知 $a,b$ 的情况下无法通过询问确定所有人的身份，则报告不可能。

否则，你可以进行不超过 $n^2$ 次询问。每次给定 $x$ 和 $y$，向 $x$ 询问 $y$ 的身份，交互库返回规则如下：

• 如果 $x$ 是诚实的，那么 $x$ 会如实返回 $y$ 的身份。
• 如果 $x$ 是不诚实的，$x$ 会任意选择回答。注意 $x$ 可以按照某种策略回答。

交互库会通过你的询问次数评分。

• 如果你未能正确判断有无解，或交互过程不合法，得 $0$ 分。
• 如果无解，得 $100$ 分。
• 否则，如果你返回的身份不正确，得 $25$ 分。
• 否则，你的得分由查询次数 $q$ 决定：

q	得分
$\leq n^2$	40
$\leq 2bn$	55
$\leq 30n$	65
$\leq 3n$	85
$\leq 2n$	100

$a+b\leq 1000$ 且 $a,b\geq 1$。

题解

一个观察是，我们能分辨身份当且仅当 $a>b$。

如果 $a\leq b$，那么我们可以从 $b$ 个假的人中选出 $a$ 个人，对这 $a$ 个人询问时按照这 $a$ 个人为真，其他都为假来回答。然后就无法判断这 $a$ 个人是真是假。

如果 $a>b$，那么对于每个人 $i$，我们询问其他所有人对他的评价。如果有 $>b$ 个人认为他是真的，那 么就是真的，否则即为假。注意到我们可以认为 $i$ 声称 $i$ 是真的，那么只要做 $2bn$ 次。

考虑去找一个真的人，然后再通过他问出所有人的身份。

因为 $a>b$，考虑类似摩尔投票的思路。

如果 $x$ 认为 $y$ 是假的，那么 $x$ 和 $y$ 中有至少一个为假，可以直接删除。

否则，如果 $x$ 和 $y$ 都认为对面是真的，那么 $x$ 和 $y$ 的种类相同。

于是有一个 $3n$ 次的做法：

• 我们维护集合 $S$，满足 $S$ 中的人的种类相同。加入一个人 $i$ 时，讨论和集合中任意一个人 $j$ 的关系。
• 如果 $i$ 认为 $j$ 假或 $j$ 认为 $i$ 假，那么可以直接删除 $i$ 和 $j$。
• 如果 $i$ 和 $j$ 都认为对面是真的，那么就把 $j$ 加入 $S$。

考虑优化。我们不需要维护一个身份相同的集合，而是维护一条链 $S_1,S_2,\cdots,S_k$，满足 $S_i$ 认为 $S_{i+1}$ 是真的。

实际上，$S_{1\sim k}$ 的真实身份一定是一段前缀是假的，剩下一段后缀是真的。

那么每次我们加入 $i$ 时，只要看 $S_k$ 是否认为 $i$ 是真的。如果是，则加入 $S$，否则删除 $S_k$ 和 $i$。

因为 $a>b$，而我们每次删除的 $S_k$ 和 $i$ 中至少有一个是假的，因此最终的 $S$ 一定包含真人，即 $S_k$ 一 定为真。

那么我们再拿 $S_k$ 把所有人问一遍即可。询问次数 $2n$。

T3-序列计数（count）

题面

给定一个长度为 $n$ 的自然数序列 $a$，满足 $0\leq a_i\leq v$。

序列还需满足 $m$ 条限制。

第 $i$ 条限制为 $\max_{l_i\leq j\leq r_i}a_j=x_i$。

请输出合法的序列 $a$ 的个数，对 $10^9+7$ 取模。

题解

对于第 $i$ 个限制，它首先约束了 $a_{l_i\sim r_i}$ 都是不超过 $x_i$ 的。

记 $lim_i$ 为 $a_i$ 的上界。这个可以直接并查集预处理。

考虑对值域扫描。

对于一个 $t$，我们在处理 $x_i=t$ 的限制时，$lim<t$ 的点都是不用管的。因为它们不可能成为一个区间的 $\max$。因此我们可以取出所有 $lim=t$ 的点和 $x_i=t$ 的限制。

那么这时限制就变成一个区间必须包含至少一个 $t$ 的点。

考虑 $dp_i$ 表示 $a_i=t$，此时 $i$ 之前的点方案数。

那么下一个 $=t$ 的点 需要满足不存在区间满足 $i\leq l\leq r\leq j$，这样的 $j$ 形如一段前缀，可以差分解决。

时间复杂度 $O(n\log n+V)$。

T4-树上查询（tree）

题面

有一棵由编号为 $1\sim n$ 的 $n$ 个节点构成的有根树，边有边权。$1$ 为根节点，节点 $i$ 的父亲为 $p_i$。对于 $2\leq i\leq n$，$i$ 与 $p_i$ 之间的边权为 $a_i$。

定义 $f(u)$ 为 子树内经过 $u$ 的最长链长度。

进行 $q$ 次操作，每次将一条边的边权加上一个正整数。

在第一次操作前和每次操作后，输出

$$\left(\sum_{u=1}^nf(u)\right)\mod(10^9+7)$$

• $1\leq n,q\leq10^5$。

• $2\leq i\leq n$ 时 $1\leq p_i<i,0\leq a_i\leq 10^9$。

• 每次操作 $1\leq x\leq n,1\leq v\leq 10^9$。

题解

$f_u$ 是 $u$ 子树内以 $u$ 为端点的最长链和与最长链无公共边的次长链之和。

对于每一个点 $u$，我们记录 $mx_u,sec_u$ 为子树内与 $1$ 距离最大值和次大值。这里次大值到 $x$ 的链需要 $mx$ 和最大值的无公共边。

考虑动态维护长链剖分，那么子树的 $mx$ 就是实链上儿子的 $mx$，次长链 $sec$ 就是虚儿子的 $mx$ 的最大值。

对于一次修改 $x$，我们先对 $x$ 子树内的 $mx$ 和 $sec$ 整体加 $v$。

然后找到 $x$ 子树内最大的深度，对于 $x$ 的所有祖先去更新。它对于长剖的影响是把 $x$ 到根链上一段后缀 变成实链。

这个是和 LCT access 类似的，一个结论是虚实边变化次数是 $O(q\log n)$ 的。证明考虑轻重链剖分，这 个就是在 dfs 序上颜色段均摊。

那么考虑去数据结构统一维护实边，暴力修改虚边。

一条实链，操作相当于对一条链的 $mx$ 加上 $v$。

对于一条虚边，操作相当于对于单点查询 $mx$ 和 $sec$，然后进行单点改。

于是我们需要支持：

• 子树加，查子树最大深度。
• 对于 $mx$ 子树加、链加，查单点。
• 对于 $sec$ 子树加，查单点。
• 动态修改一个点是否是实儿子。
• 查询一个点所在长链顶点。

第一条线段树维护，第二三条可以树状数组维护。

第四五条 std 用了倍增树状数组维护，复杂度 $O(q\log^3n)$。常数较小，可以通过。

实际上也可以用一些办法去掉一个 $\log$，做到 $O(q\log^2n)$。